package com.laotang.第_3_章_二分查找.力扣_274_H指数;

import java.util.Arrays;

public class _274_h_index {

    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(1)
    public int hIndex1(int[] citations) {
        int left = 0, right = citations.length;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;

            int cnt = 0;
            for (int i = 0; i < citations.length; i++) {
                if (citations[i] >= mid) cnt++;
            }

            if (cnt >= mid) left = mid;
            else right = mid - 1;
        }
        return left;
    }

    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(logn)
    public int hIndex2(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        // bug 修复，h 不能等于 0，否则数组越界异常
        for (int h = n; h > 0; h--) {
            if (citations[n - h] >= h) return h;
        }
        return 0;
    }

    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(logn)
    public int hIndex3(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int left = 0, right = n;
        while (left < right) {
            int h = left + (right - left + 1) / 2;
            if (citations[n - h] >= h) left = h;
            else right = h - 1;
        }
        return left;
    }

    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] counter = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++;
            } else {
                counter[citations[i]]++;
            }
        }

        int total = 0;
        for (int h = n; h >= 0; h--) {
            total += counter[h];
            if (total >= h) return h;
        }

        return 0;
    }
}
